"""P8 8.详解前缀树和贪心算法"""

from sys import maxsize

"""
图的存储方式：
1、邻接表
2、邻接矩阵


"""


class Node:
    """图中节点的类定义"""

    def __init__(self, value):
        # 节点的信息
        self.value = value
        # 本节点指向其他节点的数量
        self.out = 0
        # 其他节点指向本节点的数量
        self.enter = 0
        # List<Node> 本节点指向的其他节点列表
        self.next_nodes = list()
        # List<Edge> 本节点指向其他节点边的列表
        self.next_edges = list()


class Edge:
    """图中边的类定义"""

    def __init__(self, weight, come, go):
        # 边的权值
        self.weight = weight
        # 边出发的节点
        self.come = come
        # 边到达的节点
        self.go = go


class Graph:
    """图的类定义"""

    def __init__(self):
        # HashMap<Integer, Node> 图中所有节点的Dict映射
        self.nodes = dict()
        # HashSet<Edge> 图中所有边的Set集合
        self.edges = set()


def create_graph(matrix: list) -> Graph:
    """matrix列表中每个数据:[come节点的值，go节点的值，weight]"""
    graph = Graph()
    for line in matrix:
        come, go, weight = line
        # 节点如果不在图中，新建节点
        if come not in graph.nodes:
            graph.nodes[come] = Node(come)
        if go not in graph.nodes:
            graph.nodes[go] = Node(go)
        # 从图中获取两个节点的信息
        come_node = graph.nodes.get(come)
        go_node = graph.nodes.get(go)
        # 根据weight权值新建两个节点的边
        edge = Edge(weight, come_node, go_node)
        # 更新两个节点的部分信息
        come_node.next_nodes.append(go_node)
        come_node.next_edges.append(edge)
        come_node.out += 1
        go_node.enter += 1
        # 在图中添加边
        graph.edges.add(edge)
    return graph


"""
图的宽度优先遍历：
1、利用队列实现
2、从源节点开始依次按照宽度进队了，然后弹出
3、每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
4、循环步骤3，直到队列变空

图的深度优先遍历：
1、利用栈实现
2、从源节点开始把节点按照深度放入栈，然后弹出
3、每弹出一个节点，如果该节点存在没入栈的邻接点，
   就把该节点和下一个没有进过栈的邻接点先后人栈
4、循环步骤3，直到栈变空
"""


def graph_bfs(node: Node):
    """图的宽度优先遍历"""
    if node is None:
        return
    queue = [node]
    exist = {node}
    while queue:
        cur = queue.pop(0)
        print(cur.value)
        for i in cur.next_nodes:
            if i not in exist:
                queue.append(i)
                exist.add(i)


def graph_dfs(node: Node):
    """图的深度优先遍历"""
    if node is None:
        return
    stack = [node]
    exist = {node}
    # 这里要出来第一个节点
    print(node.value)
    while stack:
        cur = stack.pop()
        for i in cur.next_nodes:
            if i not in exist:
                print(i.value)
                stack.append(cur)
                stack.append(i)
                exist.add(i)
                break


"""
拓扑排序算法：
用于确认有向图中各个节点的依赖关系

适用范围：
要求有向图，且有入度为0的节点，且没有环
"""


def sorted_topology(graph: Graph) -> list:
    """图的拓扑排序"""
    # HashMap<Node, Integer> 表示Node的剩余入度
    enter_map = dict()
    # Queue<Node> 存放入度为0的节点
    zero_queue = list()
    for node in graph.nodes:
        enter_map[node] = node.enter
        if node.enter == 0:
            zero_queue.append(node)
    # List<Node>
    result = list()
    while zero_queue:
        cur = zero_queue.pop(0)
        result.append(cur)
        # 消除入度为0的节点，它邻接点的入度减一
        for node in cur.next_nodes:
            enter_map[node] = enter_map.get(node) - 1
            if enter_map.get(node) == 0:
                zero_queue.append(node)
    return result


"""
kruskal算法、prim算法是为了获取图中总权值最小的连接结果

kruskal算法的适用范围：
要求无向图

prim算法的适用范围：
要求无向图

kruskal算法和prim算法用于得到最小生成树
"""


class MySets:
    """简单的并查集"""

    def __init__(self, nodes: list):
        self.set_map = dict()
        for node in nodes:
            self.set_map[node] = [node]

    def is_same_set(self, node1: Node, node2: Node) -> bool:
        """判断两个节点所在的集合是否相同"""
        return self.set_map.get(node1) == self.set_map.get(node2)

    def union(self, node1: Node, node2: Node):
        """合并两个节点所在的集合"""
        set1 = self.set_map.get(node1)
        set2 = self.set_map.get(node2)
        for node in set2:
            set1.append(node)
            self.set_map[node] = set1


def kruskal(graph: Graph):
    """kruskal算法"""
    sets = MySets(list(graph.nodes))
    sort_edge = sorted(graph.edges, key=lambda x: x.weight)
    result = list()
    # 找到权值最小的边，边连接的两个节点如果不在一个集合，添加结果，合并集合
    for edge in sort_edge:
        if not sets.is_same_set(edge.come, edge.go):
            result.append(edge)
            sets.union(edge.come, edge.go)
    return result


def prim(graph: Graph):
    """prim算法"""
    # 走过的节点
    checked_node = set()
    # 可能连接的边
    min_edge = list()
    result = list()
    # 适配森林的数据情况
    for node in graph.nodes:
        if node in checked_node:
            continue
        checked_node.add(node)
        for edge in node.next_edges:
            min_edge.append(edge)
        while min_edge:
            edge = sorted(min_edge, key=lambda x: x.weight)[0]
            min_edge.remove(edge)
            if edge.go not in checked_node:
                checked_node.add(edge.go)
                result.append(edge)
                for next_edge in edge.go.next_edges:
                    min_edge.append(next_edge)


"""
Dijkstra算法：
在图中获得从head节点到其他每个节点的最小距离
适用范围：
可以有权值为负数的边，但是不能有累加权值为负数的环
"""


class Dijkstra:
    """Dijkstra算法"""

    @staticmethod
    def dijkstra(head: Node):
        distance_map = {head: 0}
        """
        distance_map的key表示从head出发到的节点，value表示到达的最小距离
        distance_map中不存在的key表示距离为正无穷
        selected_nodes表示已经求过距离的节点，以后不用再处理了
        """
        selected_nodes = set()
        min_node = Dijkstra.get_min_unselected_node(
            distance_map, selected_nodes)
        while min_node:
            distance = distance_map.get(min_node)
            # 更新min_node的邻接点的距离信息
            for edge in min_node.next_edges:
                go_node = edge.go
                if go_node in distance_map:
                    distance_map[go_node] = min(distance_map.get(go_node),
                                                distance + edge.weight)
                else:
                    distance_map[go_node] = distance + edge.weight
            selected_nodes.add(min_node)
            min_node = Dijkstra.get_min_unselected_node(
                distance_map, selected_nodes)
        return distance_map

    @staticmethod
    def get_min_unselected_node(distance_map: dict, selected_nodes: set):
        """获取distance_map中距离最小的，且不在selected_nodes中的节点"""
        min_distance = maxsize
        min_node = None
        for node, distance in distance_map.items():
            if node not in selected_nodes and distance < min_distance:
                min_distance = distance
                min_node = node
        return min_node
